package LeetCode;

import java.util.ArrayList;
import java.util.Arrays;

public class LC_354_RussianDollEnvelopes {

    public static void main(String[] args) {

    }

    static class Solution {
        public int maxEnvelopes(int[][] envelopes) {
            if (envelopes == null || envelopes.length == 0) return 0;
            Arrays.sort(envelopes, (a, b) -> {
                if (a[0] != b[0]) {
                    return a[0] - b[0];
                } else {
                    return a[1] - b[1];
                }
            });
            int max = 1;
            int[] arr = new int[envelopes.length];
            for (int i = 0; i < envelopes.length; i++) {
                arr[i] = 1;
                for (int j = i - 1; j >= 0; j--) {
                    if (envelopes[i][0] > envelopes[j][0] && envelopes[i][1] > envelopes[j][1]) {
                        arr[i] = Math.max(arr[i], arr[j] + 1);
                    }
                }
                max = Math.max(max, arr[i]);
            }
            return max;
        }
    }

    static class Solution_2 {
        public int maxEnvelopes(int[][] envelopes) {
            if (envelopes == null || envelopes.length == 0)
                return 0;

            Arrays.sort(envelopes, (a, b) -> {
                if (a[0] != b[0]) {
                    return a[0] - b[0];
                } else {
                    return b[1] - a[1];
                }
            });

            ArrayList<Integer> list = new ArrayList<>();

            for (int[] envelope : envelopes) {
                if (list.size() == 0 || list.get(list.size() - 1) < envelope[1]) list.add(envelope[1]);
                int l = 0;
                int r = list.size() - 1;
                while (l < r) {
                    int m = l + (r - l) / 2;
                    if (list.get(m) < envelope[1]) {
                        l = m + 1;
                    } else {
                        r = m;
                    }
                }
                list.set(r, envelope[1]);
            }
            return list.size();
        }
    }

}